package day28_35.day29;


import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Day29_1 {
    /**
     *	正数数组中的最小不可组成和
     *	输入：正数数组arr
     *	返回：正数数组中的最小不可组成和
     */
    // 一看就是回溯法
    // 存放所有子集和
    static List<Integer> list = new ArrayList<>();

    public static int getFirstUnFormedNum(int[] arr) {
        // 回溯所有子集
        dfs(arr, 0, 0);

        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        int min = list.get(0);
        int max = list.get(list.size() - 1);
        for (int i = min + 1; i < max; i++) {
            if(!list.contains(i)){
                return i;
            }
        }
        return max + 1;
    }

    private static void dfs(int[] arr, int startIndex, int sum) {
        // 先把之前子集和摘出去
        if(sum != 0 && !list.contains(sum)){
            list.add(sum);
        }

        //再看边界条件
        if(startIndex >= arr.length){
            return;
        }

        // 当前层往下的分支
        for (int i = startIndex; i < arr.length; i++) {
            dfs(arr, i + 1, sum + arr[i]);
        }
    }

    public static void main(String[] args) {
        int[] arr = {};
        System.out.println(getFirstUnFormedNum(arr));
    }
}